#include <bits/stdc++.h>
#include <climits>
#include <unordered_map>
using namespace std;

/*
* 统计字符串中所有字符的起始和结束位置，记录这些区间
* (实际上也就是435.无重叠区间 (opens new window)题目里的输入)，
* 将区间按左边界从小到大排序，找到边界将区间划分成组，互不重叠。
* 找到的边界就是答案。
*/

#define indexOfChar(x) (x-'a')

class Solution {
public:
    static bool cmp(vector<int> &a, vector<int> &b) {
        return a[0] < b[0];
    }

    // 记录每个字母出现的区间
    vector<vector<int>> countLabels(string s){
        vector<vector<int>> hash(26, vector<int>(2, INT_MIN));
        vector<vector<int>> hash_fliter;
        for(int i=0; i<s.size(); ++i){
            if(hash[indexOfChar(s[i])][0] == INT_MIN){
                hash[indexOfChar(s[i])][0] = i; //更新left
            }
            hash[indexOfChar(s[i])][1] = i; //更新right
        }

        // 去除字符串中未出现的字母所占用区间
        for(int i=0; i<hash.size(); ++i){
            if(hash[i][0] != INT_MIN){
                hash_fliter.push_back(hash[i]);
            }
        }
        return hash_fliter;
    }
    vector<int> partitionLabels(string s) {
        vector<int> res;
        // 这一步得到的 hash 即为无重叠区间题意中的输入样例格式：区间列表
        // 只不过现在我们要求的是区间分割点
        vector<vector<int>> hash = countLabels(s);
        // 按照左边界从小到大排序
        sort(hash.begin(), hash.end(), cmp);
        // 记录最大右边界
        int rightBoard = hash[0][1];
        int leftBoard = 0;
        for (int i = 1; i < hash.size(); ++i){
            // 由于字符串一定能分割，因此,
            // 一旦下一区间左边界大于当前右边界，即可认为出现分割点
            if (hash[i][0] > rightBoard) {
                res.push_back(rightBoard - leftBoard + 1);
                leftBoard = hash[i][0];
            }
            rightBoard = max(hash[i][1], rightBoard); //更新右边界
        }
        // 最右端
        res.push_back(rightBoard - leftBoard + 1);
        return res;
    }
};